package com.huawei.controller;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * description
 *
 * @author cwx1134046
 * @since 2023-02-15
 */
public class FindOrder {

    public static int[] findOrder(int numCourses, int[][] prerequisites) {

        List<Element> arr = new ArrayList<>(numCourses);

        for(int i = 0; i < numCourses ; i++ ) {
            Element element = new Element();
            element.index = i;
            arr.add(element);
        }

        for (int[] prerequisite : prerequisites) {
            arr.get(prerequisite[0]).courses.add(prerequisite[1]);
            arr.get(prerequisite[1]).degree = arr.get(prerequisite[1]).degree +1;
        }
        Queue<Element> queue  = new LinkedList<>();
        for (Element element : arr){
            if (element.degree == 0 ) {
                queue.offer(element);
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        while(!queue.isEmpty()){

            Element poll = queue.poll();
            result.add(poll.index);
            List<Integer> courses = poll.courses;
            for (Integer course : courses) {
                Element element = arr.get(course);
                element.degree = element.degree - 1;
                if(element.degree == 0){
                    queue.offer(element);
                }
            }

        }

        if(result.size() < numCourses){
            return new int[]{};
        } else {
            int[] ints = new int[numCourses];
            for(int i = 0 ;i <numCourses;i++){
                ints[i] = result.get(result.size()-1 - i);
            }
            return ints;
        }
    }


    static class Element {
        List<Integer> courses = new ArrayList<>();
        Integer degree = 0;
        Integer index = 0;
    }

    public static void main(String[] args) {
       // numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
        findOrder(4,new int[][]{{1,0},{2,0},{3,1},{3,2}});
    }


}
